1735F - Pebbles and Beads - CodeForces Solution

/*
Problem: 1735F
Date: 19-01-2024 05:47 AM
*/


#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

using ftype = long double;

// Note: seg is short for segment and plural of seg is sex
struct seg {
    ll p; ll q;
    mutable ftype len;
    seg(ll p, ll q, ftype len = 2.) : p(p), q(q), len(len) {}
    bool operator<(const seg &o) const {
        return p * o.q < o.p * q;
    }
};

using sex_machine = multiset<seg>;

struct pt {
    ftype x, y;
    pt(ftype x = 0, ftype y = 0) : x(x), y(y) {};
    pt operator+(const pt &o) const {
        return pt(x + o.x, y + o.y);
    }
    pt operator-(const pt &o) const {
        return pt(x - o.x, y - o.y);
    }
    pt operator*(const ftype f) const {
        return pt(x * f, y * f);
    }
};

void solve() {
    int n;
    ll a, b;
    cin >> n >> a >> b;
    vector<ll> p(n), q(n);
    rep(i, 0, n) cin >> p[i];
    rep(i, 0, n) cin >> q[i];
    pt p_first(0, b), p_last(a, 0);
    sex_machine sex;
    if(a > 0) sex.insert(seg(a, 0, 1));
    if(b > 0) sex.insert(seg(0, -b, 1));
    cout << fixed << setprecision(8);
    rep(i, 0, n) {
        sex.insert(seg(p[i], -q[i], 2.));
        p_first = p_first - pt(p[i], -q[i]);
        p_last = p_last + pt(p[i], -q[i]);
        while(p_first.x < 0) {
            assert(!sex.empty());
            auto it = sex.begin();
            pt p_second = p_first + pt(it->p, it->q) * it->len;
            if(p_second.x < 0) {
                sex.erase(it);
                p_first = p_second;
                continue;
            }
            assert(it->p != 0);
            it->len = p_second.x / it->p;
            p_first.x = 0;
            p_first.y = p_second.y - it->q * it->len;
        }
        while(p_last.y < 0) {
            assert(!sex.empty());
            auto it = prev(sex.end());
            pt p_second = p_last - pt(it->p, it->q) * it->len;
            if(p_second.y < 0) {
                sex.erase(it);
                p_last = p_second;
                continue;
            }
            assert(it->q != 0);
            it->len = p_second.y / -it->q;
            p_last.y = 0;
            p_last.x = p_second.x + it->p * it->len;
        }
        cout << p_last.x << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}